import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.Set;

/**
 * This class will represent a modified linear probing hash table. 
 * The modification is specified in the comments for the put method.
 */
public class HashTable<K,V> {
	
	/**
	 * Constant determining the max load factor
	 */
	private final double MAX_LOAD_FACTOR = 0.71;
	
	/**
	 * Constant determining the initial table size
	 */
	private final int INITIAL_TABLE_SIZE = 11;
	
	/**
	 * Number of elements in the table
	 */
	private int size;
	
	/**
	 * The backing array of this hash table
	 */
	private MapEntry<K,V>[] table;
	
	/**
	 * Initialize the instance variables
	 * Initialize the backing array to the initial size given
	 */
	public HashTable() {
		table = new MapEntry[INITIAL_TABLE_SIZE];
		size = 0;
	}
	
	/**
	 * Add the key value pair in the form of a MapEntry
	 * Use the default hash code function for hashing
	 * This is a linear probing hash table so put the entry in the table accordingly
	 * 
	 * Make sure to use the given max load factor for resizing
	 * Also, resize by doubling and adding one. In other words:
	 * 
	 * newSize = (oldSize * 2) + 1
	 *
	 * The load factor should never exceed maxLoadFactor at any point. So if adding this element
	 * will cause the load factor to be exceeded, you should resize BEFORE adding it. Otherwise
	 * do not resize.
	 * 
	 * IMPORTANT Modification: If the given key already exists in the table
	 * then set it as the next entry for the already existing key. This means
	 * that you will never be replacing values in the hashtable, only adding or removing.
	 * This is similar to external chaining
	 * 
	 * @param key This will never be null
	 * @param value This can be null
	 */
	public void put(K key,V value){
		MapEntry<K,V> newEntry = new MapEntry<K,V>(key,value);
		if (((size+1.0)/table.length) > MAX_LOAD_FACTOR) {
			resize();
		}
		if (contains(key)) {
			for (int i = 0; i < table.length; i++) {
				if (table[i] != null) {
					if (table[i].getKey().equals(key)) {
						MapEntry<K,V> current = table[i];
						while (current.getNext() != null) current = current.getNext();
						current.setNext(newEntry);
						current.setRemoved(false);
					}
				}
					
			}
		}
		else {
			int index = findIndex(Math.abs(key.hashCode() % table.length));
			table[index] = newEntry;
			newEntry.setRemoved(true);
		}
		size++;
	}
	
	private int findIndex(int index) {
		if (table[index] == null) return index; 
		else {
			return findIndex((index +1) % table.length);
		}
	}
	
	private void resize() {
		MapEntry<K,V>[] newTable = new MapEntry[2*table.length + 1];
		MapEntry<K,V>[] oldTable = table;
		table = newTable;
		size = 0;
		for (int i = 0; i < oldTable.length; i++) {
			if (oldTable[i] != null) {
				put(oldTable[i].getKey(), oldTable[i].getValue());
				//System.out.println("resize: size = " + size);
				MapEntry<K,V> current = oldTable[i];
				while (current.getNext() != null) {
					current = current.getNext();
					put(current.getKey(), current.getValue());
				}
			}
		}
	}
	
	
	/**
	 * Remove the entry with the given key.
	 * 
	 * If there are multiple entries with the same key then remove the last one
	 * 
	 * @param key
	 * @return The value associated with the key removed
	 */
	public V remove(K key){
		for (int i = 0; i < table.length; i++) {
			if (table[i] != null) {
				if (table[i].getKey().equals(key)) {
					if (table[i].getNext() == null) {
						V value = table[i].getValue();
						table[i] = null;
						size--;
						return value;
					}
					MapEntry<K,V> current = table[i];
					MapEntry<K,V> prev = table[i];
					//System.out.println("First current key: " + current.getKey() + " and value: " + current.getValue());
					while (current.getNext() != null) current = current.getNext();
					//System.out.println("2nd  current key: " + current.getKey() + " and value: " + current.getValue());
					if (prev.getNext() != null) {
						while (!prev.getNext().equals(current)) prev = prev.getNext();
					}
					
					//System.out.println("Previous key: " + prev.getKey() + " and value: " + prev.getValue());
					V value = current.getValue();
					if (current.equals(table[i].getNext())) table[i].setRemoved(true);
					prev.setNext(null);
					current = null;
					
					size--;
					return value;
				}
			}
			
		}
		return null;
	}
	
	
	/**
	 * Checks whether an entry with the given key exists in the hash table
	 * 
	 * @param key
	 * @return
	 */
	public boolean contains(K key){
		if (size == 0) return false;
		else if (key == null) return false;
		for (MapEntry<K,V> entry: table) {
			if (entry != null) {
				if (entry.getKey().equals(key)) return true;
			}
		}
		return false;
	}
	
	/**
	 * Return a collection of all the values
	 * 
	 * We recommend using an ArrayList here
	 *
	 * @return 
	 */
	public Collection<V> values(){
		ArrayList<V> list = new ArrayList<V>(size);
		for (MapEntry<K,V> entry: table) {
			if (entry != null) {
				list.add(entry.getValue());
				MapEntry<K,V> current = entry;
				while (current.getNext() != null) {
					current = current.getNext();
					list.add(current.getValue());
				}
			}
			
			
		}
		return list;
	}
	
	/**
	 * Return a set of all the distinct keys
	 * 
	 * We recommend using a HashSet here
	 * 
	 * Note that the map can contain multiple entries with the same key
	 * 
	 * @return
	 */
	public Set<K> keySet(){
		HashSet<K> set = new HashSet<K>();
		for (MapEntry<K,V> entry: table) {
			if (entry != null) set.add(entry.getKey());
		}
		return set;
	}
	
	/**
	 * Return the number of values associated with one key
	 * Return -1 if the key does not exist in this table
	 * @param key
	 * @return
	 */
	public int keyValues(K key){
		if (!contains(key)) return -1;
		int count = 0;
		for (MapEntry<K,V> entry: table) {
			
			if (entry != null) {
				if (entry.getKey().equals(key)) {
					count++;
					MapEntry<K,V> current = entry;
					while (current.getNext() != null) {
						current = current.getNext();
						count++;
					}
				}
			}
				
			
		}
		
		return count;
	}
	
	/**
	 * Return a set of all the unique key-value entries
	 * 
	 * Note that two map entries with both the same key and value
	 * could exist in the map.
	 * 
	 * @return
	 */
	public Set<MapEntry<K,V>> entrySet(){
		HashSet<MapEntry<K,V>> set = new HashSet<MapEntry<K,V>>();
		for (int i = 0; i < table.length; i++) {
			if (table[i] != null) {
				set.add(table[i]);
				MapEntry<K,V> current = table[i];
				while (current.getNext() != null) {
					current = current.getNext();
					set.add(current);
				}
			}
		}
		return set;
	}
	
	/**
	 * Clears the hash table
	 */
	public void clear(){
		MapEntry<K,V>[] t = new MapEntry[INITIAL_TABLE_SIZE];
		setTable(t);
	}
	
	/*
	 * The following methods will be used for grading purposes do not modify them
	 */
	
	public int size(){
		return size;
	}
	
	public void setSize(int size) {
		this.size = size;
	}
	
	public MapEntry<K, V>[] getTable() {
		return table;
	}
	
	public void setTable(MapEntry<K, V>[] table) {
		this.table = table;
	}
}